数据结构之旅(3) - 队列 - Java语言描述

队列的定义

像栈一样，队列（queue）也是表。只不过它限制了插入在一端进行而删除则在另一端进行。

队列的基本操作是enqueue(入队)，它是在表的末端（叫作队尾（rear））插入一个元素；dequeue(出队)，它是删除（并返回）表的开头（叫作表头（front））的元素。

队列的实现

和栈类似，任何可以用来实现表的方式都可以实现队列，对于每一种操作，链表实现和数组实现都给出快速的O(1)运行时间。队列的链表实现是最简单直接的，大家可以动手试一试。下面就将着重研究队列的数组实现，包括了 普通数组实现 和 循环数组 实现。

普通数组实现

在操作队列时，我们要能够直接索引到队列的头部和尾部以完成 enqueue 和 dequeue 操作。对于数组 arr 而言，我们就得存储队列头部 front 和尾部 rear 的 index，而且这样一来，队列元素的个数可以也可以用 rear - front + 1 快速的计算得出！队列为空的条件就是 front = rear。

对于 enqueue 操作而言，我们只需将 arr[++rear] = value；对于 dequeue 操作而言， 我们只需将 front++，可以说是十分方便。

但由于数组的长度是固定的，所以我们在使用普通数组实现队列之前，要估算一下数据规模，避免空间需求大于数组长度的情况。不过，我们可以用另一种方法：循环数组实现队列，这个方法不仅可以从一定程度上解决空间不够的问题，还避免了由于 dequeue 而造成的空间的浪费！

循环数组实现

循环数组不是一种新型的ADT，循环数组仍是一个普通的数组。循环二字指的是 空间上的循环：在 rear 指向队尾（rear++ 将是一个不存在的位置）并且接收到了 enqueue 操作时，rear 绕回至数组的头部 继续进行存储操作。它的 enqueue 和 dequeue 操作和普通数组实现队列的操作方式一样，唯一区别就是在 rear = arr.length - 1 这个特殊的位置上！

用循环数组实现队列从一定程度上解决了空间不够的问题，但也不是意味着完全不需要去考虑数组容量。真正可以完全不用考虑容量问题的是用链表来实现队列。

具体代码实现

普通数组实现

/**
 * 简单数组实现队列.
 * 仅实现入队和出队操作：
 *      1. enqueue  入队
 *      2. dequeue  出队
 *      3. size    队列大小
 *
 * 图个方便：
 * 	1. 数据类型选取 int 类型
 *	2. private + getter&&setter -> public
 */
class SimpleArrayQueue {

    public int front;    //队首
    public int rear;     //队尾
    public int[] arr;    //用作队列的数组
    public int maxSize;  //队列元素个数最大值

    //根据size初始化一个数组用来实现队列
    public SimpleArrayQueue(int size) {
        this.front = 0; //初始化队首
        this.rear = 0; //初始化队尾
        this.arr = new int[size]; //初始化数组
        this.maxSize = size; //设置最大容量
    }

    //入队
    public void enqueue(int value) {
        if (rear != maxSize - 1) { //判断是否已到队尾
            this.arr[++rear] = value; //先 ++rear 再 赋值
        } else {
            System.out.println("数组容量不够 !!!");
        }
    }

    //出队
    public int dequeue() {
        if(front != rear) { //判断队列是否为空
            return this.arr[front++]; //先取值 arr[front] 再 front++
        } else {
            System.out.println("队列为空 !!!");
            return Integer.MIN_VALUE; //队列为空返回int的最小值
        }
    }

    //获取队列大小
    public int size() {
        if(front == rear) {
            return 0;
        } else {
            return rear - front + 1;
        }
    }
    
}

循环数组实现

/**
 * 循环数组实现队列.
 * 仅实现入队和出队操作：
 *      1. enqueue  入队
 *      2. dequeue  出队
 *      3. size    队列大小
 *
 * 图个方便：
 * 	1. 数据类型选取 int 类型
 *	2. private + getter&&setter -> public
 */
class CircularArrayQueue {

    public int front;        //队首
    public int rear;         //队尾
    public int[] arr;        //用作队列的数组
    public int maxSize;      //队列元素个数最大值
    public int currentSize;  //当前队列大小

    //根据size初始化一个数组用来实现队列
    public SimpleArrayQueue(int size) {
        this.front = 0; //初始化队首
        this.rear = 0; //初始化队尾
        this.arr = new int[size]; //初始化数组
        this.maxSize = size; //设置最大容量
        this.currentSize = 0; //初始化当前容量

    }

    //入队
    public void enqueue(int value) {
        if(this.currentSize < this.maxSize) { //判断是否已达到最大容量
            if(rear != this.maxSize - 1) { //判断是否到达队尾
                this.arr[++rear] = value;
            } else {
                rear = 0; //"循环"至队头
                this.arr[rear] = value; //赋值
            }
            this.currentSize++; //当前队列大小+1
        } else {
            System.out.println("数组容量不够 !!!");
        }
    }

    //出队
    public int dequeue() {
        if(this.currentSize != 0) { //判断队列是否为空
            this.currentSize--;
            if(front != this.maxSize - 1) { //判断是否在队尾
                return this.arr[front++];
            } else {
                int temp = this.arr[front];
                front = 0; //"循环"至队头
                return temp;
            }
        } else {
            System.out.println("队列为空 !!!");
            return Integer.MIN_VALUE;
        }
    }

    //获取队列大小
    public int size() {
        return this.currentSize;
    }

}

一些小练习（顺序随机）

1. 用两个栈来实现一个队列，完成队列的Push和Pop操作。

2. 约瑟夫问题I

3. 约瑟夫问题II